• Formal Definition: The art or science concerning the principles, means, and methods for rendering plain information unintelligible, and for restoring encrypted information to intelligible form. (National Information Systems Security (INFOSEC) Glossary, 1999)
• Informal: The basic objective of cryptography is to enable two people, whom are usually referred to as Alice and Bob in the text that I read, to communicate over an insecure channel in such a way that an opponent, usually referred to as Oscar, cannot understand what is being said. This channel could be a telephone line or computer network, for example.

• The information that Alice sends to Bob, which is called plaintext, can be English text, numerical data, zeros and ones, or anything at all – its structure is completely arbitrary.
• Alice encrypts the plaintext, using a predetermined key, and sends the resulting ciphertext over the channel.
• Oscar, upon seeing the ciphertext in the channel by eavesdropping, cannot determine what the plaintext was.
• But Bob, who knows the key, can decrypt the ciphertext and reconstruct the plaintext.

This concept leads us to the following definition.

• A cryptosystem is a five-tuple (P, C, K, E, D), where the following conditions are satisfied:

1. P is a finite set of possible plaintexts.
2. C is a finite set of possible ciphertexts.
3. K, the keyspace, is a finite set of possible keys.
4. For each kÎ K, there is an encryption rule e_kÎ E and a corresponding decryption rule d_kÎ D. Each e_k: P® C and d_k: C® P are functions such that d_k(e_k(x)) = x for all plaintext xÎ P.

• Cryptosystems can be broadly classified into symmetric-key systems and public-key systems.
• A public-key system uses two keys, a public key to encrypt the messages and a private key to decrypt them.
• (say how we will discuss much more about these tomorrow)
• A symmetric-key system, or secret-key system, in contrast is a cryptosystem in which the sender and the receiver of a message, share a single common key that is used to encrypt and decrypt messages.
• (this is what we will talk about today)

For today, we will be assuming that Alice and Bob have chosen a random key and exchanged secretly either in person or over a secure line. Now lets get to some simple cryptosystems. I will go through this first basic cryptosystem in excrutiating depth in order to really give a feel for what is going on.

• The idea behind shift cipher is based on closure and inverses of addition in the group Z_m, where m is a positive integer.
• We will use shift cipher to encrypt ordinary English text by setting up a correspondence between alphabetic characters and residues modulo 26 as follows A« 0, B« 1, …, Z« 25.
• Shift Cipher is defined by P = C = K = Z₂₆. For 0 £ k £ 25, define

and

d_k(y) = (y – k) (modulo 26)

for all x,yÎ Z₂₆.

• Properties 1, 2, and 3 are clearly met, i.e., the set of plaintexts, the set of ciphertexts, and the keyspace all are finite.
• We must check property 4.

1. Let kÎ K and xÎ P, arbitrary.
2. d_k(e_k(x)) = d_k((x + k)(mod 26)) = ((x + k) – k) (mod 26) = x (mod 26) = x.

• Therefore, Shift Cipher is in fact a cryptosystem.

Here’s a simple example of the shift cipher in action. We will refer to the correspondences below for the example.

• Suppose the key is k = 11, and the plaintext to be sent is

• We first convert the plaintext to a sequence of integers using the above correspondence, obtaining the following:

• Next, we add 11 to each value modulo 26 to yield:

• Finally, we convert the sequence of integers to alphabetic characters, obtaining the ciphertext:

• This is the message that is sent. To decrypt the ciphertext, Bob will first convert the ciphertext to a sequence of integers, then subtract 11 from each value (mod 26), and finally convert the sequence of integers to alphabetic characters.

I’m sure that all of us have seen puzzles like this in the newspaper or puzzle books and realize that this is not a difficult system to break. Just trying all the keys, although cumbersome, would not be difficult in the Shift Cipher, that is one of the reasons, in practice, it is not secure. The process of attempting to compute the key k, given a string of ciphertext, is called cryptanalysis. In general, we want cryptosystems in which an exhaustive key search is impossible(even for computers).

Now lets study a cryptosystem that has more algebra involved and a larger keyspace.

• In the affine cipher, we restrict our encryption function to functions of the form:

• These functions are called affine functions, hence the name.
• In order that decryption is possible, it is necessary to ask when an affine function is one-to-one. In other words, for any yÎ Z₂₆, we want the congruence

ax + b º y (mod 26) to have a unique solution for x.

• This congruence is equivalent to ax º (y – b) (mod 26)
• Now, as y varies over Z₂₆, so, too, does y – b vary over Z₂₆. Hence, it suffices to study the congruence ax º y (mod 26), for yÎ Z₂₆, i.e., if this congruence holds for all yÎ Z₂₆, then it will also hold for all y – b, if bÎ Z₂₆, because y – bÎ Z₂₆.

Trying out some elements of Z₂₆, we start to discover that only some values of a have this property.

Claim: This congruence has a unique solution for every y if and only if gcd(a,26) = 1.

Proof

• ‘Þ ’ Suppose the congruence has a unique solution for every y.

1. (RAA) Assume gcd(a,26) ¹ 1.

Note: a can be 0 because 0x º 0 (mod 26), has 26 solutions.

2. Then gcd(a,26) = d > 1.
3. Thus the congruence ax º 0 (mod 26) has at least two distinct solutions, namely x = 0 and x = 26/d, for the particular y = 0. x = 0 works obviously. Because d | a and d | 26, therefore, $ m,nÎ Z₂₆ such that dm = a and dn = 26.

So 26/d = n. And an = (dm)n = (dn)m = 26m º 0 (mod 26).

This is a contradiction.

4. Therefore, gcd(a,26) = 1.

• ‘Ü ’ Suppose gcd(a,26) = 1.

0. Assume x₁, x_2Î Z₂₆, such that ax₁ º ax₂ (mod 26)
1. Then a(x₁ – x₂) º 0 (mod 26)
2. Thus, 26 | a(x₁ – x₂).
3. By Lemma (*), or simply by division property, since 26 | a(x₁ – x₂), and gcd(a,26) = 1, we must therefore have that 26 | (x₁ – x₂).

For example, since gcd(4,26) = 2, it follows that e_k(x) = 4x + 7 is not a valid encryption function: x and x + 13 will encrypt to the same value, for any xÎ Z₂₆. Specifically,

e_k(a) = e_k(0) = 4(0) + 7 (mod 26) = 7, and e_k(n) = e_k(13) = 4(13) + 7 (mod 26) = 7.

Lemma(*): If a,b,cÎ Z₂₆ such that gcd(a,b) = 1 and a | bc, then a | c.

Proof

• a | bc Þ $ nÎ Z₂₆ such that an º bc (mod 26).
• gcd(a,b) = 1 Þ $ r,sÎ Z₂₆ such that ar + bs º 1 (mod 26).

• (arc + bcs) º c (mod 26) (multiplying by c, distributing, associativity of ring)
• arc + ans º c (mod 26) (substitute an for bc)
• a(rc + ns) º c (mod 26) (distribution in Z₂₆)
• rc + ns (mod 26)Î Z₂₆, thus a | c.

Thm. The congruence ax º b (mod m) has a unique solution xÎ Z_m if and only if gcd(a,m) = 1.

So we have shown that the only one-to-one affine functions in Z₂₆ are those of the form ax + b (mod m) where gcd(a,m) = 1 and bÎ Z₂₆.

We have shown that the Affine Cipher satisfies the first 3 properties of the definition of a cryptosystem and that it satisfies the need for a one-to-one encryption rule, but we still need an associate decryption rule in order to decrypt the ciphertext.

• Consider our congruence y º ax + b (mod 26). This is equivalent to

• It turns out that the a values which have a multiplicative inverse modulo 26 are exactly those which satisfy gcd(a,26) = 1.

• Since in encryption the a always satisfies this condition.
• Thus, x º a^-1(y – b) (mod 26), which is the form of the decryption function

Lemma(*2): Let a and n be integers, with n > 1. Then a has a multiplicative inverse modulo n if and only if gcd(a,n) = 1.

Proof

• ‘Þ ’ First, suppose that a has an inverse modulo n.

0. Then there is a k such that ak º 1 (mod n).
1. Thus, n is a divisor of ak – 1, so there must be some integer t so that

ak – 1 º nt (mod n).

2. Rewriting this as ak – nt º 1(mod n), we see that gcd(a,n) = 1.

• ‘Ü ’ Now, suppose that gcd(a,n) = 1. Then there are integers r and s with

0. This means ar – 1 is divisible by n.
1. So ar º 1 (mod n).
2. This tells us r is the inverse of a.

Putting this all together, we finally obtain our Affine Cipher.

• The Affine Cipher is defined by P = C = Z₂₆ and let

For k = (a,b)Î K, define

e_k(x) = (ax + b) (mod 26)

and d_k(y) = a^-1(y – b) (mod 26), for all x,yÎ Z₂₆.

• We must check property 4.

1. Let k = (a,b)Î K and xÎ P, arbitrary.
2. d_k(e_k(x)) = d_k((ax + b)(mod 26)) = a^-1((ax + b) – b) (mod 26)

• Therefore, the affine cipher is indeed a cryptosystem.

• We want to send the word, dog, using the key k = (3,5), gcd(3,26) = 1, so this key is okay.
• We get the corresponding integers as before: 3, 14, 6.
• Then we multiply by 3 and add 5 modulo 26 to yield: 14, 21, 23, so the message is: OVX.
• 3^-1 = 9, so to decrypt we take the ciphertext corresponding integers and subtract 5 then multiply by 9 modulo 26 to get back to: 3, 14, 6.

• First a definition, the number of integers in Z_m that are relatively prime to m is often denoted by f (m)(this function is called the Euler phi-function).
• In the Affine Cipher, the number of choices for b is m, and the number of choices for a is f (m). Thus, the number of keys in the keyspace for the Affine Cipher over Z_m is mf (m).
• In the special case where m = 26, f (26) = 12 (1,3,5,7,9,11,15,17,19,21,23,and 25 are all relatively prime to 26), so the size of the keyspace = 26(12) = 312, which is larger, but not secure by any means.

Note: In both the Shift Cipher and the Affine Cipher, once a key is chosen, each alphabetic character is mapped to a unique alphabetic character. For this reason, these cryptosystems are called monoalphabetic. These type of systems are easy to break by simply looking for the most common letters in the ciphertext and trying out the most common English letters in their place until an intelligible message is formed.

The following cryptosystem corrects these faults by offering a polyalphabetic approach to encryption.

• The Vigenere Cipher was invented in the sixteenth century, and is associated with the idea of adding a keyword of length m to the plaintext that is to be sent.
• This cipher encrypts m alphabetic characters at a time.
• The Vigenere Cipher is defined by P = C = K = (Z₂₆)^m.

• Verifications that this is a cryptosystem is left to the reader.

• Suppose m = 7 and the keyword is ENCRYPT. This corresponds to the numerical key k = (4, 13, 2, 17, 24, 15, 19). And suppose the plaintext is:

• We convert to plaintext and add the key modulo 26, as follows:

19	7	8	18	18	24	18	19	4	12	18	4	2	20	17	4
4	13	2	17	24	15	19	4	13	2	17	24	15	19	4	13

23

20

10

9

16

13

11

23

17

14

9

2

17

13

21

17

• This turns into the ciphertext: XUKJQNLXROJCRNVR
• Decryption is done in the same manner, just subtracting the keyword instead of adding.

• The Vigenere Cipher has a keyspace of 26^m, for a keyword of length m.
• For our example the keyspace is 26⁷ = 8031810176.
• This makes it a lot more difficult to do an exhaustive key search.
• Unfortunately, there are other forms of cryptanalysis and the Vigenere Cipher becomes susceptible to many types if the ciphertext is long.

Let’s build another polyalphabetic cryptosystem this time using some linear algebra.

• The strategy behind the Hill Cipher is to take m linear combinations of the m alphabetic characters a plaintext, producing m alphabetic characters in a ciphertext.
• The idea is that if we have a plaintext string of length m, (x₁, x₂, …, x_m)

and m linear combinations: k₁₁x₁ + k₁₂x₂ + … + k_1mx_m

k₂₁x₁ + k₂₂x₂ + … + k_2mx_m

…

k_m1x₁ + k_m2x₂ + … + k_mmx_m

Then we can get (y₁, y₂, …, y_m) by:

, where k_ijÎ Z₂₆.

• This system seems fine until we consider decryption.
• In order, to retrieve the plaintext from a ciphertext we are going to need the inverse of the encryption matrix, i.e., if y = Ax, then we want to find A^-1 such that x = A^-1y.
• If all the entries are in a field then we know that the invertible matrices are exactly the ones in the general linear group, however, Z₂₆ is not a field, so what do we do.
• From linear algebra, we know that a real matrix K has an inverse if and only if its determinant is non-zero. We need to find some sort of analygous idea in Z₂₆.

Claim: A matrix K has an inverse modulo 26 if and only if gcd(det K, 26) = 1.

Proof

• ‘Þ ’ First, suppose that gcd(det K, 26) = 1.

0. Then the det K has an inverse in Z₂₆. (We proved this earlier)
1. Now, for 1 £ i £ m, 1 £ j £ m, define K_ij to be the matrix obtained from K by deleting the ith row and the jth column.
2. Define a matrix K* to have as its (i,j)-entry the value (-1)^i+jdet K_ji.
3. Then it can be shown that K^-1 = (det K)^-1K*. (skipping over stuff here)
4. Hence, K has an inverse.

• ‘Ü ’ Now, suppose that K has an inverse, K^-1.

0. 1 = det I = det (KK^-1) = det K det K^-1
1. Thus, det K is invertible in Z₂₆.
2. Therefore, gcd(det K, 26) = 1.

• The Hill Cipher is defined by, for some fixed positive integer m, P = C = (Z₂₆)^m, and let K = { A : A is an m x m matrix and gcd(det A, 26) = 1}

• Verifications that this is a cryptosystem is left to the reader.

• Let m = 2 and take , to encrypt the plaintext: hello
• First we break up the word into pairs, adding a dummy character, say ‘r’ in the case of an odd number of characters. This yields: he ll or.
• Converting to integers we get: (7 4) (11 11) (14 17)
• A(7 4) mod 26 = (0 5), A(11 11) mod 26 = (3 24), A(14 17) mod 26 = (1 3)
• The associated ciphertext is: AFDYBD
• det A mod 26 = -17 mod 26 = 9, gcd(9, 26) = 1, so A has an inverse.
• We can get the inverse by taking the normal inverse in Z and then taking modulus 26.
• 
• To recover the plaintext we convert the ciphertext to integer pairs and apply A^-1.
• A^-1(0 5) mod 26 = (7 4), A^-1(3 24) mod 26 = (11 11), A^-1(1 3) = (14 17) and we are back to where we started.